package org.lex.utils.collections;

import java.io.IOException;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.Enumeration;
import java.util.Hashtable;

/**
 * <p>
 * Provide storage mechanism for key-value pairs. In most cases this will be an
 * array of alternating key-value pairs. As it grows larger it is scaled up to a
 * Hashtable.
 * </p>
 * <p>
 * This does no synchronization, if you need thread safety synchronize on
 * another object before calling this.
 * </p>
 */
public class ArrayTable implements Cloneable {
	// Our field for storage
	private Object table = null;
	private static final int ARRAY_BOUNDARY = 8;

	/*
	 * Put the key-value pair into storage
	 */
	public void put(Object key, Object value) {
		if (table == null) {
			table = new Object[] { key, value };
		} else {
			int size = size();
			if (size < ARRAY_BOUNDARY) { // We are an array
				if (containsKey(key)) {
					Object[] tmp = (Object[]) table;
					for (int i = 0; i < tmp.length - 1; i += 2) {
						if (tmp[i].equals(key)) {
							tmp[i + 1] = value;
							break;
						}
					}
				} else {
					Object[] array = (Object[]) table;
					int i = array.length;
					Object[] tmp = new Object[i + 2];
					System.arraycopy(array, 0, tmp, 0, i);
					tmp[i] = key;
					tmp[i + 1] = value;
					table = tmp;
				}
			} else { // We are a hashtable
				if ((size == ARRAY_BOUNDARY) && isArray()) {
					grow();
				}
				((Hashtable) table).put(key, value);
			}
		}
	}

	/**
	 * @param key
	 * @return the value to which the specified key is mapped, or {@code null}
	 *         if no mapping for the key
	 */
	public Object get(Object key) {
		Object value = null;
		if (table != null) {
			if (isArray()) {
				Object[] array = (Object[]) table;
				for (int i = 0; i < array.length - 1; i += 2) {
					if (array[i].equals(key)) {
						value = array[i + 1];
						break;
					}
				}
			} else {
				value = ((Hashtable) table).get(key);
			}
		}
		return value;
	}

	/*
	 * Returns the number of pairs in storage
	 */
	public int size() {
		int size;
		if (table == null)
			return 0;
		if (isArray()) {
			size = ((Object[]) table).length / 2;
		} else {
			size = ((Hashtable) table).size();
		}
		return size;
	}

	/**
	 * Returns true if we have a value for the key.<br>
	 * We use Object.equals(Object) method to identify keys
	 */
	public boolean containsKey(Object key) {
		boolean contains = false;
		if (table != null) {
			if (isArray()) {
				Object[] array = (Object[]) table;
				for (int i = 0; i < array.length - 1; i += 2) {
					if (array[i].equals(key)) {
						contains = true;
						break;
					}
				}
			} else {
				contains = ((Hashtable) table).containsKey(key);
			}
		}
		return contains;
	}

	/*
	 * Removes the key and its value Returns the value for the pair removed
	 */
	public Object remove(Object key) {
		Object value = null;
		if (key == null) {
			return null;
		}
		if (table != null) {
			if (isArray()) {
				// Is key on the list?
				int index = -1;
				Object[] array = (Object[]) table;
				for (int i = array.length - 2; i >= 0; i -= 2) {
					if (array[i].equals(key)) {
						index = i;
						value = array[i + 1];
						break;
					}
				}
				// If so, remove it
				if (index != -1) {
					Object[] tmp = new Object[array.length - 2];
					// Copy the list up to index
					System.arraycopy(array, 0, tmp, 0, index);
					// Copy from two past the index, up to
					// the end of tmp (which is two elements
					// shorter than the old list)
					if (index < tmp.length)
						System.arraycopy(array, index + 2, tmp, index, tmp.length - index);
					// set the listener array to the new array or null
					table = (tmp.length == 0) ? null : tmp;
				}
			} else {
				value = ((Hashtable) table).remove(key);
			}
			if (size() == ARRAY_BOUNDARY - 1 && !isArray()) {
				shrink();
			}
		}
		return value;
	}

	/**
	 * Removes all the mappings.
	 */
	public void clear() {
		table = null;
	}

	/*
	 * Returns a clone of the <code>ArrayTable</code>.
	 */
	public Object clone() {
		ArrayTable newArrayTable = new ArrayTable();
		if (isArray()) {
			Object[] array = (Object[]) table;
			for (int i = 0; i < array.length - 1; i += 2) {
				newArrayTable.put(array[i], array[i + 1]);
			}
		} else {
			Hashtable tmp = (Hashtable) table;
			Enumeration keys = tmp.keys();
			while (keys.hasMoreElements()) {
				Object o = keys.nextElement();
				newArrayTable.put(o, tmp.get(o));
			}
		}
		return newArrayTable;
	}

	/**
	 * Returns the keys of the table, or <code>null</code> if there are
	 * currently no bindings.
	 * 
	 * @param keys
	 *            array of keys
	 * @return an array of bindings
	 */
	public Object[] getKeys(Object[] keys) {
		if (table == null) {
			return null;
		}
		if (isArray()) {
			Object[] array = (Object[]) table;
			if (keys == null) {
				keys = new Object[array.length / 2];
			}
			for (int i = 0, index = 0; i < array.length - 1; i += 2, index++) {
				keys[index] = array[i];
			}
		} else {
			Hashtable tmp = (Hashtable) table;
			Enumeration enum_ = tmp.keys();
			int counter = tmp.size();
			if (keys == null) {
				keys = new Object[counter];
			}
			while (counter > 0) {
				keys[--counter] = enum_.nextElement();
			}
		}
		return keys;
	}

	/*
	 * Returns true if the current storage mechanism is an array of alternating
	 * key-value pairs.
	 */
	private boolean isArray() {
		return (table instanceof Object[]);
	}

	/*
	 * Grows the storage from an array to a hashtable.
	 */
	private void grow() {
		Object[] array = (Object[]) table;
		Hashtable tmp = new Hashtable(array.length / 2);
		for (int i = 0; i < array.length; i += 2) {
			tmp.put(array[i], array[i + 1]);
		}
		table = tmp;
	}

	/*
	 * Shrinks the storage from a hashtable to an array.
	 */
	private void shrink() {
		Hashtable tmp = (Hashtable) table;
		Object[] array = new Object[tmp.size() * 2];
		Enumeration keys = tmp.keys();
		int j = 0;
		while (keys.hasMoreElements()) {
			Object o = keys.nextElement();
			array[j] = o;
			array[j + 1] = tmp.get(o);
			j += 2;
		}
		table = array;
	}

	/**
	 * Writes the passed in ArrayTable to the passed in ObjectOutputStream. The
	 * data is saved as an integer indicating how many key/value pairs are being
	 * archived, followed by the the key/value pairs. If <code>table</code> is
	 * null, 0 will be written to <code>s</code>.
	 * <p>
	 * This is a convenience method that ActionMap/InputMap and AbstractAction
	 * use to avoid having the same code in each class.
	 */
	static void writeArrayTable(ObjectOutputStream s, ArrayTable table) throws IOException {
		Object keys[];
		if (table == null || (keys = table.getKeys(null)) == null) {
			s.writeInt(0);
		} else {
			// Determine how many keys have Serializable values, when
			// done all non-null values in keys identify the Serializable
			// values.
			int validCount = 0;
			for (int counter = 0; counter < keys.length; counter++) {
				if ((keys[counter] instanceof Serializable) && (table.get(keys[counter]) instanceof Serializable)) {
					validCount++;
				} else {
					keys[counter] = null;
				}
			}
			// Write ou the Serializable key/value pairs.
			s.writeInt(validCount);
			if (validCount > 0) {
				for (int counter = 0; counter < keys.length; counter++) {
					if (keys[counter] != null) {
						s.writeObject(keys[counter]);
						s.writeObject(table.get(keys[counter]));
						if (--validCount == 0) {
							break;
						}
					}
				}
			}
		}
	}
}
